// 78.子集/全排列[dfs]
// https://leetcode-cn.com/problems/subsets/
// https://leetcode-cn.com/problems/permutations/
// 78. 子集
// 中等,给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
// 示例 1：
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 示例 2：
// 输入：nums = [0]
// 输出：[[],[0]]

class Solution {
 public:
  vector<vector<int>> ans;
  vector<int> arr;
  void dfs(vector<int>& nums, int cur) {
    ans.push_back(arr);  //细节1
    for (int i = cur; i < nums.size(); i++) {
      arr.push_back(nums[i]);
      dfs(nums, i + 1);  //细节3
      arr.pop_back();
    }
  }
  vector<vector<int>> subsets(vector<int>& nums) {
    dfs(nums, 0);
    return ans;
  }
};
// 全排列
class Solution {
 public:
  vector<vector<int>> ans;
  vector<int> arr;
  bool vis[100010];  //标记下标，用于去重
  void dfs(vector<int>& nums, int cur) {
    if (cur >= nums.size()) {
      ans.push_back(arr);
      return;
    }
    for (int i = 0; i < nums.size(); i++) {
      if (!vis[i]) {
        arr.push_back(nums[i]);
        vis[i] = 1;
        dfs(nums, cur + 1);
        arr.pop_back();
        vis[i] = 0;
      }
    }
  }
  vector<vector<int>> permute(vector<int>& nums) {
    dfs(nums, 0);
    return ans;
  }
};
